1. Field of the Invention
The present invention relates to the making of a digital map database in general and in particular to a consolidation method called "conflation" which requires the identification of matching features on two digital maps--vertices, arcs, and areas--for combining geometric and attribute data from the two digital map sources into one ultimate map.
2. Description of the Related Art
Quality digital maps are vital in many applications. They must provide sufficient positional accuracy as well as a whole variety of application attributes: city/street/road names, driving restrictions, addresses, company and business location, hotels, restaurants, etc. Customers may require additional features and attributes for their specific purposes, but there is no universal single source of all the data.
Source data for maps comes from federal, state and local governments and private businesses. Many exist in a variety of digital formats and differ a great deal in kind, quantity, and accuracy of the data attached. Different maps usually have a certain common core of geographic features, yet they may represent quite different points of view on the same area. For example, one map might have a lot of detail with respect to the bodies of water located therein, e.g. their names, shape, hydrological profile, etc, but not have anything related to political and administrative subdivisions of the area. Another map may have all the lake and river names omitted, but contain important county, city and ZIP-code information. Another typical situation is where one of the available maps has very good positional accuracy but has few attributes attached, while another one provides plenty of attributes but has inferior geographical coordinate accuracy. Even if both maps are geographically identical (i.e., are represented by the same set of vertices, arcs, and areas) they may differ substantially in terms of the quality and quantity of attributes. However, people often need both attributes and accuracy on the same map. All this implies is that there is a necessity to obtain all the valuable information from several maps in order to produce the "ultimate" map that comprises the best from all of the maps.
To combine the information from two digital maps related to the same area requires a special procedure called conflation. To date, such work has been performed manually by superimposing both maps on a computer screen. An operator identifies the potentially corresponding elements and makes all necessary changes, e.g. adds and deletes arcs and vertices as well as assigns and removes the attributes. This is a tedious, time consuming and costly process. Automation of conflation is beneficial, especially when a series of updates takes place. This, of course, necessitates handling the positional and/or topological inadequacy between the maps and discrepancies between the attributes.
Conflation and compilation are both used to denote the creation of a map from various sources. Whereas compilation connotes an editorial assembly of pieces of data from various sources, conflation connotes a scholarly investigation to determine the common source for variants of a text or oral tradition and in terms of map making has as its goal a more accurate and complete representation of the earth's surface than is provided by any of the sources used. The result is a higher quality map since common errors are accordingly more rare.
Conflation requires the identification of matching features, vertices, arcs, and areas, on at least two source maps.
A conflation program needs to be able to identify "the same" features on both maps, but a naive attempt to match vertices by their coordinates immediately fails. One reason for this is that the distance between two objectively matchable points in both maps is, in many cases, greater than the length of a street block. There are also quite a few cases where names (which are generally a rather robust attribute) are absent or distorted, or represent the alternate names of the same street ("El Camino Real" and "Route 82" in the San Francisco Bay Area, for example). For such reasons, simple straightforward matching often fails.
Two general approaches to the matching problem have been explored. One is called a "constructive" or local approach and the other is called a global approach.
In the local approach, see, for example, A. Saalfeld, Conflation Automated Map Compilation, Int. J. Geographical Information Systems, 1988, Vol 2, No. 3, pp. 217-228, it is assumed that a first algorithm identifies relatively reliable subsets of matched vertices from both maps as a first step. A second algorithm then travels from previously matched points to their neighbors, and tries to establish a match at a new pair of vertices. Therefore, the points are identified as mutually matched by a connecting path that is also matched.
Among the hidden obstacles in this method is that starting from one point, there are multiple paths to another point, which requires the use of a sorting function to select the appropriate path and, as might be suspected, different paths yield different values. As a result, it is difficult to set up adequate criteria for inclusion of the new pair into the matched set.
The global approach also consists of two stages. A global set of all potentially matchable elements is created and stored in a relational database. Then a number of filters are used to remove all false or dubious matches. The advantage of the global method is that very simple criteria can be used for eliminating the false or doubtful potential matches. For example, in the United States it has been found that street and road names provide an adequate tool for such filtering. However, a principal disadvantage of the global method is that it requires the creation and maintenance of a run-time database whose size may be comparable to the size of the original maps.